// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
// // 创建新节点
// TreeNode* CreateNode(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         perror("Memory allocation failed");
//         exit(EXIT_FAILURE);
//     }
//     newNode->value = value;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入节点（二叉搜索树规则）
// TreeNode* InsertNode(TreeNode* root, DataType x) {
//     if (root == NULL) {
//         return CreateNode(x);
//     }
//     if (x < root->value) {
//         root->left = InsertNode(root->left, x);
//     } else {
//         root->right = InsertNode(root->right, x);
//     }
//     return root;
// }
//
// //先序遍历
// void PreOrder(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->value);
//         PreOrder(root->left);
//         PreOrder(root->right);
//     }
// }
//
// // 释放内存
// void FreeTree(TreeNode* root) {
//     if (root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// bool X(TreeNode* root,DataType x) {
//     if(root==NULL) {
//         return false;
//     }
//     // 如果找到目标节点，返回true
//     if(x==root->value) {
//         return true;
//     }
//     // 如果在左子树或右子树中找到目标节点
//     if(X(root->left,x)||X(root->right,x)) {
//         printf("%d ",root->value);// 打印当前祖先节点
//         return true;
//     }
//     return false;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int length = sizeof(values) / sizeof(values[0]);
//
//     // 构建二叉搜索树
//     for (int i = 0; i < length; i++) {
//         root = InsertNode(root, values[i]);
//     }
//
//     X(root,40);
//
//     FreeTree(root);
//     return 0;
// }